package demo;

/**
 * @Author liangzai
 * @Description:
 */
public class Training {
    //最深叶节点的最近公共祖先
    public static TreeNode lcaDeepestLeaves(TreeNode root) {
        maxDeep = deep(root) - 1;
        return lcaDeepestLeaves(root,0);
    }

    static int maxDeep = 0;
    public static TreeNode lcaDeepestLeaves(TreeNode root,int deep) {
        if (root == null){
            return null;
        }
        int left = deep(root.left) + deep;
        int right = deep(root.right) + deep;
        if (left == right && left == maxDeep){
            return root;
        }
        return left == maxDeep ? lcaDeepestLeaves(root.left,deep + 1) : lcaDeepestLeaves(root.right,deep + 1);
    }

    public static int deep(TreeNode root) {
        if (root == null){
            return 0;
        }
        return 1 + Math.max(deep(root.left),deep(root.right));
    }

    //字符串转换整数 (atoi)
    public int myAtoi(String s) {
        int n = s.length(), i = 0;
        long res = 0;
        // 去除前导零
        while (i < n && s.charAt(i) == ' ') i++;
        if (i == n) return 0;
        // 判断符号
        int flag = 1;
        if (s.charAt(i) == '+') i++;
        else if (s.charAt(i) == '-') {flag = -1; i++;}
        // 收获结果
        for (; i < n; i++) {
            char c = s.charAt(i);
            if (c < '0' || c > '9') break;
            res = res * 10 + flag * (c - '0');
            if (res <= Integer.MIN_VALUE) return Integer.MIN_VALUE;
            if (res >= Integer.MAX_VALUE) return Integer.MAX_VALUE;
        }
        return (int) res;
    }
}
